Resonance Algorithm: A New Look at the Shortest Path Problem

分类： 数学 >> 应用数学 分类： 计算机科学 >> 计算机软件 分类： 信息科学与系统科学 >> 信息与系统科学其他学科 提交时间： 2021-10-11

Liu, Yu Lin, Qiguang Hong, Binbin Hjerpe, Daniel Liu, Xiaofeng

摘要： The shortest path problem (SPP) is a classic problem and appears in a wide range of applications. Although a variety of algorithms already exist, new advances are still being made, mainly tuned for particular scenarios to have better performances. As a result, they become more and more technically complex and sophisticated. Here we developed a novel nature-inspired algorithm to compute all possible shortest paths between two nodes in a graph: Resonance Algorithm (RA), which is surprisingly simple and intuitive. Besides its simplicity, RA turns out to be much more time-efficient for large-scale graphs than the extended Dijkstra's algorithm (such that it gives all possible shortest paths). Moreover, RA can handle any undirected, directed, or mixed graphs, irrespective of loops, unweighted or positively-weighted edges, and can be implemented in a fully decentralized manner. These good properties ensure RA a wide range of applications.

同行评议状态:待评议

 点击量 16023  下载量 1428  评论